<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html lang="en">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <title>LCOV - Lua 5.3.5 - src/ltablib.c</title>
  <link rel="stylesheet" type="text/css" href="../gcov.css">
</head>

<body>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="title">LCOV - code coverage report</td></tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>

    <tr>
      <td width="100%">
        <table cellpadding=1 border=0 width="100%">
          <tr>
            <td width="10%" class="headerItem">Current view:</td>
            <td width="35%" class="headerValue"><a href="../index.html">top level</a> - <a href="index.html">src</a> - ltablib.c</td>
            <td width="5%"></td>
            <td width="15%"></td>
            <td width="10%" class="headerCovTableHead">Hit</td>
            <td width="10%" class="headerCovTableHead">Total</td>
            <td width="15%" class="headerCovTableHead">Coverage</td>
          </tr>
          <tr>
            <td class="headerItem">Test:</td>
            <td class="headerValue">Lua 5.3.5</td>
            <td></td>
            <td class="headerItem">Lines:</td>
            <td class="headerCovTableEntry">169</td>
            <td class="headerCovTableEntry">193</td>
            <td class="headerCovTableEntryMed">87.6 %</td>
          </tr>
          <tr>
            <td class="headerItem">Date:</td>
            <td class="headerValue">2019-06-13 19:44:17</td>
            <td></td>
          </tr>
          <tr>
            <td class="headerItem">Legend:</td>
            <td class="headerValueLeg">            Lines:
            <span class="coverLegendCov">hit</span>
            <span class="coverLegendNoCov">not hit</span>
</td>
            <td></td>
          </tr>
          <tr><td><img src="../glass.png" width=3 height=3 alt=""></td></tr>
        </table>
      </td>
    </tr>

    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  </table>

  <table cellpadding=0 cellspacing=0 border=0>
    <tr>
      <td><br></td>
    </tr>
    <tr>
      <td>
<pre class="sourceHeading">          Line data    Source code</pre>
<pre class="source">
<span class="lineNum">       1 </span>            : /*
<span class="lineNum">       2 </span>            : ** $Id: ltablib.c,v 1.93.1.1 2017/04/19 17:20:42 roberto Exp $
<span class="lineNum">       3 </span>            : ** Library for Table Manipulation
<span class="lineNum">       4 </span>            : ** See Copyright Notice in lua.h
<span class="lineNum">       5 </span>            : */
<span class="lineNum">       6 </span>            : 
<span class="lineNum">       7 </span>            : #define ltablib_c
<span class="lineNum">       8 </span>            : #define LUA_LIB
<span class="lineNum">       9 </span>            : 
<span class="lineNum">      10 </span>            : #include &quot;lprefix.h&quot;
<span class="lineNum">      11 </span>            : 
<span class="lineNum">      12 </span>            : 
<span class="lineNum">      13 </span>            : #include &lt;limits.h&gt;
<span class="lineNum">      14 </span>            : #include &lt;stddef.h&gt;
<span class="lineNum">      15 </span>            : #include &lt;string.h&gt;
<span class="lineNum">      16 </span>            : 
<span class="lineNum">      17 </span>            : #include &quot;lua.h&quot;
<span class="lineNum">      18 </span>            : 
<span class="lineNum">      19 </span>            : #include &quot;lauxlib.h&quot;
<span class="lineNum">      20 </span>            : #include &quot;lualib.h&quot;
<span class="lineNum">      21 </span>            : 
<span class="lineNum">      22 </span>            : 
<span class="lineNum">      23 </span>            : /*
<span class="lineNum">      24 </span>            : ** Operations that an object must define to mimic a table
<span class="lineNum">      25 </span>            : ** (some functions only need some of them)
<span class="lineNum">      26 </span>            : */
<span class="lineNum">      27 </span>            : #define TAB_R   1                       /* read */
<span class="lineNum">      28 </span>            : #define TAB_W   2                       /* write */
<span class="lineNum">      29 </span>            : #define TAB_L   4                       /* length */
<span class="lineNum">      30 </span>            : #define TAB_RW  (TAB_R | TAB_W)         /* read/write */
<span class="lineNum">      31 </span>            : 
<span class="lineNum">      32 </span>            : 
<span class="lineNum">      33 </span>            : #define aux_getn(L,n,w) (checktab(L, n, (w) | TAB_L), luaL_len(L, n))
<span class="lineNum">      34 </span>            : 
<span class="lineNum">      35 </span>            : 
<span class="lineNum">      36 </span><span class="lineNoCov">          0 : static int checkfield (lua_State *L, const char *key, int n) {</span>
<span class="lineNum">      37 </span><span class="lineNoCov">          0 :   lua_pushstring(L, key);</span>
<span class="lineNum">      38 </span><span class="lineNoCov">          0 :   return (lua_rawget(L, -n) != LUA_TNIL);</span>
<span class="lineNum">      39 </span>            : }
<span class="lineNum">      40 </span>            : 
<span class="lineNum">      41 </span>            : 
<span class="lineNum">      42 </span>            : /*
<span class="lineNum">      43 </span>            : ** Check that 'arg' either is a table or can behave like one (that is,
<span class="lineNum">      44 </span>            : ** has a metatable with the required metamethods)
<span class="lineNum">      45 </span>            : */
<span class="lineNum">      46 </span><span class="lineCov">      17971 : static void checktab (lua_State *L, int arg, int what) {</span>
<span class="lineNum">      47 </span><span class="lineCov">      17971 :   if (lua_type(L, arg) != LUA_TTABLE) {  /* is it not a table? */</span>
<span class="lineNum">      48 </span><span class="lineCov">          1 :     int n = 1;  /* number of elements to pop */</span>
<span class="lineNum">      49 </span><span class="lineCov">          1 :     if (lua_getmetatable(L, arg) &amp;&amp;  /* must have metatable */</span>
<span class="lineNum">      50 </span><span class="lineNoCov">          0 :         (!(what &amp; TAB_R) || checkfield(L, &quot;__index&quot;, ++n)) &amp;&amp;</span>
<span class="lineNum">      51 </span><span class="lineNoCov">          0 :         (!(what &amp; TAB_W) || checkfield(L, &quot;__newindex&quot;, ++n)) &amp;&amp;</span>
<span class="lineNum">      52 </span><span class="lineNoCov">          0 :         (!(what &amp; TAB_L) || checkfield(L, &quot;__len&quot;, ++n))) {</span>
<span class="lineNum">      53 </span><span class="lineNoCov">          0 :       lua_pop(L, n);  /* pop metatable and tested metamethods */</span>
<span class="lineNum">      54 </span>            :     }
<span class="lineNum">      55 </span>            :     else
<span class="lineNum">      56 </span><span class="lineCov">          1 :       luaL_checktype(L, arg, LUA_TTABLE);  /* force an error */</span>
<span class="lineNum">      57 </span>            :   }
<span class="lineNum">      58 </span><span class="lineCov">      17970 : }</span>
<span class="lineNum">      59 </span>            : 
<span class="lineNum">      60 </span>            : 
<span class="lineNum">      61 </span>            : #if defined(LUA_COMPAT_MAXN)
<span class="lineNum">      62 </span>            : static int maxn (lua_State *L) {
<span class="lineNum">      63 </span>            :   lua_Number max = 0;
<span class="lineNum">      64 </span>            :   luaL_checktype(L, 1, LUA_TTABLE);
<span class="lineNum">      65 </span>            :   lua_pushnil(L);  /* first key */
<span class="lineNum">      66 </span>            :   while (lua_next(L, 1)) {
<span class="lineNum">      67 </span>            :     lua_pop(L, 1);  /* remove value */
<span class="lineNum">      68 </span>            :     if (lua_type(L, -1) == LUA_TNUMBER) {
<span class="lineNum">      69 </span>            :       lua_Number v = lua_tonumber(L, -1);
<span class="lineNum">      70 </span>            :       if (v &gt; max) max = v;
<span class="lineNum">      71 </span>            :     }
<span class="lineNum">      72 </span>            :   }
<span class="lineNum">      73 </span>            :   lua_pushnumber(L, max);
<span class="lineNum">      74 </span>            :   return 1;
<span class="lineNum">      75 </span>            : }
<span class="lineNum">      76 </span>            : #endif
<span class="lineNum">      77 </span>            : 
<span class="lineNum">      78 </span>            : 
<span class="lineNum">      79 </span><span class="lineCov">         59 : static int tinsert (lua_State *L) {</span>
<span class="lineNum">      80 </span><span class="lineCov">         59 :   lua_Integer e = aux_getn(L, 1, TAB_RW) + 1;  /* first empty element */</span>
<span class="lineNum">      81 </span>            :   lua_Integer pos;  /* where to insert new element */
<span class="lineNum">      82 </span><span class="lineCov">         59 :   switch (lua_gettop(L)) {</span>
<span class="lineNum">      83 </span><span class="lineCov">         52 :     case 2: {  /* called with only 2 arguments */</span>
<span class="lineNum">      84 </span><span class="lineCov">         52 :       pos = e;  /* insert new element at the end */</span>
<span class="lineNum">      85 </span><span class="lineCov">         52 :       break;</span>
<span class="lineNum">      86 </span>            :     }
<span class="lineNum">      87 </span><span class="lineCov">          6 :     case 3: {</span>
<span class="lineNum">      88 </span>            :       lua_Integer i;
<span class="lineNum">      89 </span><span class="lineCov">          6 :       pos = luaL_checkinteger(L, 2);  /* 2nd argument is the position */</span>
<span class="lineNum">      90 </span><span class="lineCov">          6 :       luaL_argcheck(L, 1 &lt;= pos &amp;&amp; pos &lt;= e, 2, &quot;position out of bounds&quot;);</span>
<span class="lineNum">      91 </span><span class="lineCov">         11 :       for (i = e; i &gt; pos; i--) {  /* move up elements */</span>
<span class="lineNum">      92 </span><span class="lineCov">          7 :         lua_geti(L, 1, i - 1);</span>
<span class="lineNum">      93 </span><span class="lineCov">          7 :         lua_seti(L, 1, i);  /* t[i] = t[i - 1] */</span>
<span class="lineNum">      94 </span>            :       }
<span class="lineNum">      95 </span><span class="lineCov">          4 :       break;</span>
<span class="lineNum">      96 </span>            :     }
<span class="lineNum">      97 </span><span class="lineCov">          1 :     default: {</span>
<span class="lineNum">      98 </span><span class="lineCov">          1 :       return luaL_error(L, &quot;wrong number of arguments to 'insert'&quot;);</span>
<span class="lineNum">      99 </span>            :     }
<span class="lineNum">     100 </span>            :   }
<span class="lineNum">     101 </span><span class="lineCov">         56 :   lua_seti(L, 1, pos);  /* t[pos] = v */</span>
<span class="lineNum">     102 </span><span class="lineCov">         56 :   return 0;</span>
<span class="lineNum">     103 </span>            : }
<span class="lineNum">     104 </span>            : 
<span class="lineNum">     105 </span>            : 
<span class="lineNum">     106 </span><span class="lineCov">          5 : static int tremove (lua_State *L) {</span>
<span class="lineNum">     107 </span><span class="lineCov">          5 :   lua_Integer size = aux_getn(L, 1, TAB_RW);</span>
<span class="lineNum">     108 </span><span class="lineCov">          5 :   lua_Integer pos = luaL_optinteger(L, 2, size);</span>
<span class="lineNum">     109 </span><span class="lineCov">          5 :   if (pos != size)  /* validate 'pos' if given */</span>
<span class="lineNum">     110 </span><span class="lineCov">          3 :     luaL_argcheck(L, 1 &lt;= pos &amp;&amp; pos &lt;= size + 1, 1, &quot;position out of bounds&quot;);</span>
<span class="lineNum">     111 </span><span class="lineCov">          4 :   lua_geti(L, 1, pos);  /* result = t[pos] */</span>
<span class="lineNum">     112 </span><span class="lineCov">          7 :   for ( ; pos &lt; size; pos++) {</span>
<span class="lineNum">     113 </span><span class="lineCov">          3 :     lua_geti(L, 1, pos + 1);</span>
<span class="lineNum">     114 </span><span class="lineCov">          3 :     lua_seti(L, 1, pos);  /* t[pos] = t[pos + 1] */</span>
<span class="lineNum">     115 </span>            :   }
<span class="lineNum">     116 </span><span class="lineCov">          4 :   lua_pushnil(L);</span>
<span class="lineNum">     117 </span><span class="lineCov">          4 :   lua_seti(L, 1, pos);  /* t[pos] = nil */</span>
<span class="lineNum">     118 </span><span class="lineCov">          4 :   return 1;</span>
<span class="lineNum">     119 </span>            : }
<span class="lineNum">     120 </span>            : 
<span class="lineNum">     121 </span>            : 
<span class="lineNum">     122 </span>            : /*
<span class="lineNum">     123 </span>            : ** Copy elements (1[f], ..., 1[e]) into (tt[t], tt[t+1], ...). Whenever
<span class="lineNum">     124 </span>            : ** possible, copy in increasing order, which is better for rehashing.
<span class="lineNum">     125 </span>            : ** &quot;possible&quot; means destination after original range, or smaller
<span class="lineNum">     126 </span>            : ** than origin, or copying to another table.
<span class="lineNum">     127 </span>            : */
<span class="lineNum">     128 </span><span class="lineCov">          7 : static int tmove (lua_State *L) {</span>
<span class="lineNum">     129 </span><span class="lineCov">          7 :   lua_Integer f = luaL_checkinteger(L, 2);</span>
<span class="lineNum">     130 </span><span class="lineCov">          7 :   lua_Integer e = luaL_checkinteger(L, 3);</span>
<span class="lineNum">     131 </span><span class="lineCov">          6 :   lua_Integer t = luaL_checkinteger(L, 4);</span>
<span class="lineNum">     132 </span><span class="lineCov">          5 :   int tt = !lua_isnoneornil(L, 5) ? 5 : 1;  /* destination table */</span>
<span class="lineNum">     133 </span><span class="lineCov">          5 :   checktab(L, 1, TAB_R);</span>
<span class="lineNum">     134 </span><span class="lineCov">          5 :   checktab(L, tt, TAB_W);</span>
<span class="lineNum">     135 </span><span class="lineCov">          4 :   if (e &gt;= f) {  /* otherwise, nothing to move */</span>
<span class="lineNum">     136 </span>            :     lua_Integer n, i;
<span class="lineNum">     137 </span><span class="lineCov">          4 :     luaL_argcheck(L, f &gt; 0 || e &lt; LUA_MAXINTEGER + f, 3,</span>
<span class="lineNum">     138 </span>            :                   &quot;too many elements to move&quot;);
<span class="lineNum">     139 </span><span class="lineCov">          4 :     n = e - f + 1;  /* number of elements to move */</span>
<span class="lineNum">     140 </span><span class="lineCov">          4 :     luaL_argcheck(L, t &lt;= LUA_MAXINTEGER - n + 1, 4,</span>
<span class="lineNum">     141 </span>            :                   &quot;destination wrap around&quot;);
<span class="lineNum">     142 </span><span class="lineCov">          7 :     if (t &gt; e || t &lt;= f || (tt != 1 &amp;&amp; !lua_compare(L, 1, tt, LUA_OPEQ))) {</span>
<span class="lineNum">     143 </span><span class="lineCov">         12 :       for (i = 0; i &lt; n; i++) {</span>
<span class="lineNum">     144 </span><span class="lineCov">          9 :         lua_geti(L, 1, f + i);</span>
<span class="lineNum">     145 </span><span class="lineCov">          9 :         lua_seti(L, tt, t + i);</span>
<span class="lineNum">     146 </span>            :       }
<span class="lineNum">     147 </span>            :     }
<span class="lineNum">     148 </span>            :     else {
<span class="lineNum">     149 </span><span class="lineCov">          4 :       for (i = n - 1; i &gt;= 0; i--) {</span>
<span class="lineNum">     150 </span><span class="lineCov">          3 :         lua_geti(L, 1, f + i);</span>
<span class="lineNum">     151 </span><span class="lineCov">          3 :         lua_seti(L, tt, t + i);</span>
<span class="lineNum">     152 </span>            :       }
<span class="lineNum">     153 </span>            :     }
<span class="lineNum">     154 </span>            :   }
<span class="lineNum">     155 </span><span class="lineCov">          4 :   lua_pushvalue(L, tt);  /* return destination table */</span>
<span class="lineNum">     156 </span><span class="lineCov">          4 :   return 1;</span>
<span class="lineNum">     157 </span>            : }
<span class="lineNum">     158 </span>            : 
<span class="lineNum">     159 </span>            : 
<span class="lineNum">     160 </span><span class="lineCov">      80901 : static void addfield (lua_State *L, luaL_Buffer *b, lua_Integer i) {</span>
<span class="lineNum">     161 </span><span class="lineCov">      80901 :   lua_geti(L, 1, i);</span>
<span class="lineNum">     162 </span><span class="lineCov">      80901 :   if (!lua_isstring(L, -1))</span>
<span class="lineNum">     163 </span><span class="lineCov">          2 :     luaL_error(L, &quot;invalid value (%s) at index %d in table for 'concat'&quot;,</span>
<span class="lineNum">     164 </span>            :                   luaL_typename(L, -1), i);
<span class="lineNum">     165 </span><span class="lineCov">      80899 :   luaL_addvalue(b);</span>
<span class="lineNum">     166 </span><span class="lineCov">      80899 : }</span>
<span class="lineNum">     167 </span>            : 
<span class="lineNum">     168 </span>            : 
<span class="lineNum">     169 </span><span class="lineCov">      11979 : static int tconcat (lua_State *L) {</span>
<span class="lineNum">     170 </span>            :   luaL_Buffer b;
<span class="lineNum">     171 </span><span class="lineCov">      11979 :   lua_Integer last = aux_getn(L, 1, TAB_R);</span>
<span class="lineNum">     172 </span>            :   size_t lsep;
<span class="lineNum">     173 </span><span class="lineCov">      11978 :   const char *sep = luaL_optlstring(L, 2, &quot;&quot;, &amp;lsep);</span>
<span class="lineNum">     174 </span><span class="lineCov">      11978 :   lua_Integer i = luaL_optinteger(L, 3, 1);</span>
<span class="lineNum">     175 </span><span class="lineCov">      11978 :   last = luaL_optinteger(L, 4, last);</span>
<span class="lineNum">     176 </span><span class="lineCov">      11978 :   luaL_buffinit(L, &amp;b);</span>
<span class="lineNum">     177 </span><span class="lineCov">      80903 :   for (; i &lt; last; i++) {</span>
<span class="lineNum">     178 </span><span class="lineCov">      68927 :     addfield(L, &amp;b, i);</span>
<span class="lineNum">     179 </span><span class="lineCov">      68925 :     luaL_addlstring(&amp;b, sep, lsep);</span>
<span class="lineNum">     180 </span>            :   }
<span class="lineNum">     181 </span><span class="lineCov">      11976 :   if (i == last)  /* add last value (if interval was not empty) */</span>
<span class="lineNum">     182 </span><span class="lineCov">      11974 :     addfield(L, &amp;b, i);</span>
<span class="lineNum">     183 </span><span class="lineCov">      11976 :   luaL_pushresult(&amp;b);</span>
<span class="lineNum">     184 </span><span class="lineCov">      11976 :   return 1;</span>
<span class="lineNum">     185 </span>            : }
<span class="lineNum">     186 </span>            : 
<span class="lineNum">     187 </span>            : 
<span class="lineNum">     188 </span>            : /*
<span class="lineNum">     189 </span>            : ** {======================================================
<span class="lineNum">     190 </span>            : ** Pack/unpack
<span class="lineNum">     191 </span>            : ** =======================================================
<span class="lineNum">     192 </span>            : */
<span class="lineNum">     193 </span>            : 
<span class="lineNum">     194 </span><span class="lineCov">          2 : static int pack (lua_State *L) {</span>
<span class="lineNum">     195 </span>            :   int i;
<span class="lineNum">     196 </span><span class="lineCov">          2 :   int n = lua_gettop(L);  /* number of elements to pack */</span>
<span class="lineNum">     197 </span><span class="lineCov">          2 :   lua_createtable(L, n, 1);  /* create result table */</span>
<span class="lineNum">     198 </span><span class="lineCov">          2 :   lua_insert(L, 1);  /* put it at index 1 */</span>
<span class="lineNum">     199 </span><span class="lineCov">          5 :   for (i = n; i &gt;= 1; i--)  /* assign elements */</span>
<span class="lineNum">     200 </span><span class="lineCov">          3 :     lua_seti(L, 1, i);</span>
<span class="lineNum">     201 </span><span class="lineCov">          2 :   lua_pushinteger(L, n);</span>
<span class="lineNum">     202 </span><span class="lineCov">          2 :   lua_setfield(L, 1, &quot;n&quot;);  /* t.n = number of elements */</span>
<span class="lineNum">     203 </span><span class="lineCov">          2 :   return 1;  /* return table */</span>
<span class="lineNum">     204 </span>            : }
<span class="lineNum">     205 </span>            : 
<span class="lineNum">     206 </span>            : 
<span class="lineNum">     207 </span><span class="lineCov">          6 : static int unpack (lua_State *L) {</span>
<span class="lineNum">     208 </span>            :   lua_Unsigned n;
<span class="lineNum">     209 </span><span class="lineCov">          6 :   lua_Integer i = luaL_optinteger(L, 2, 1);</span>
<span class="lineNum">     210 </span><span class="lineCov">          6 :   lua_Integer e = luaL_opt(L, luaL_checkinteger, 3, luaL_len(L, 1));</span>
<span class="lineNum">     211 </span><span class="lineCov">          6 :   if (i &gt; e) return 0;  /* empty range */</span>
<span class="lineNum">     212 </span><span class="lineCov">          5 :   n = (lua_Unsigned)e - i;  /* number of elements minus 1 (avoid overflows) */</span>
<span class="lineNum">     213 </span><span class="lineCov">          5 :   if (n &gt;= (unsigned int)INT_MAX  || !lua_checkstack(L, (int)(++n)))</span>
<span class="lineNum">     214 </span><span class="lineNoCov">          0 :     return luaL_error(L, &quot;too many results to unpack&quot;);</span>
<span class="lineNum">     215 </span><span class="lineCov">         13 :   for (; i &lt; e; i++) {  /* push arg[i..e - 1] (to avoid overflows) */</span>
<span class="lineNum">     216 </span><span class="lineCov">          8 :     lua_geti(L, 1, i);</span>
<span class="lineNum">     217 </span>            :   }
<span class="lineNum">     218 </span><span class="lineCov">          5 :   lua_geti(L, 1, e);  /* push last element */</span>
<span class="lineNum">     219 </span><span class="lineCov">          5 :   return (int)n;</span>
<span class="lineNum">     220 </span>            : }
<span class="lineNum">     221 </span>            : 
<span class="lineNum">     222 </span>            : /* }====================================================== */
<span class="lineNum">     223 </span>            : 
<span class="lineNum">     224 </span>            : 
<span class="lineNum">     225 </span>            : 
<span class="lineNum">     226 </span>            : /*
<span class="lineNum">     227 </span>            : ** {======================================================
<span class="lineNum">     228 </span>            : ** Quicksort
<span class="lineNum">     229 </span>            : ** (based on 'Algorithms in MODULA-3', Robert Sedgewick;
<span class="lineNum">     230 </span>            : **  Addison-Wesley, 1993.)
<span class="lineNum">     231 </span>            : ** =======================================================
<span class="lineNum">     232 </span>            : */
<span class="lineNum">     233 </span>            : 
<span class="lineNum">     234 </span>            : 
<span class="lineNum">     235 </span>            : /* type for array indices */
<span class="lineNum">     236 </span>            : typedef unsigned int IdxT;
<span class="lineNum">     237 </span>            : 
<span class="lineNum">     238 </span>            : 
<span class="lineNum">     239 </span>            : /*
<span class="lineNum">     240 </span>            : ** Produce a &quot;random&quot; 'unsigned int' to randomize pivot choice. This
<span class="lineNum">     241 </span>            : ** macro is used only when 'sort' detects a big imbalance in the result
<span class="lineNum">     242 </span>            : ** of a partition. (If you don't want/need this &quot;randomness&quot;, ~0 is a
<span class="lineNum">     243 </span>            : ** good choice.)
<span class="lineNum">     244 </span>            : */
<span class="lineNum">     245 </span>            : #if !defined(l_randomizePivot)          /* { */
<span class="lineNum">     246 </span>            : 
<span class="lineNum">     247 </span>            : #include &lt;time.h&gt;
<span class="lineNum">     248 </span>            : 
<span class="lineNum">     249 </span>            : /* size of 'e' measured in number of 'unsigned int's */
<span class="lineNum">     250 </span>            : #define sof(e)          (sizeof(e) / sizeof(unsigned int))
<span class="lineNum">     251 </span>            : 
<span class="lineNum">     252 </span>            : /*
<span class="lineNum">     253 </span>            : ** Use 'time' and 'clock' as sources of &quot;randomness&quot;. Because we don't
<span class="lineNum">     254 </span>            : ** know the types 'clock_t' and 'time_t', we cannot cast them to
<span class="lineNum">     255 </span>            : ** anything without risking overflows. A safe way to use their values
<span class="lineNum">     256 </span>            : ** is to copy them to an array of a known type and use the array values.
<span class="lineNum">     257 </span>            : */
<span class="lineNum">     258 </span><span class="lineNoCov">          0 : static unsigned int l_randomizePivot (void) {</span>
<span class="lineNum">     259 </span><span class="lineNoCov">          0 :   clock_t c = clock();</span>
<span class="lineNum">     260 </span><span class="lineNoCov">          0 :   time_t t = time(NULL);</span>
<span class="lineNum">     261 </span>            :   unsigned int buff[sof(c) + sof(t)];
<span class="lineNum">     262 </span><span class="lineNoCov">          0 :   unsigned int i, rnd = 0;</span>
<span class="lineNum">     263 </span><span class="lineNoCov">          0 :   memcpy(buff, &amp;c, sof(c) * sizeof(unsigned int));</span>
<span class="lineNum">     264 </span><span class="lineNoCov">          0 :   memcpy(buff + sof(c), &amp;t, sof(t) * sizeof(unsigned int));</span>
<span class="lineNum">     265 </span><span class="lineNoCov">          0 :   for (i = 0; i &lt; sof(buff); i++)</span>
<span class="lineNum">     266 </span><span class="lineNoCov">          0 :     rnd += buff[i];</span>
<span class="lineNum">     267 </span><span class="lineNoCov">          0 :   return rnd;</span>
<span class="lineNum">     268 </span>            : }
<span class="lineNum">     269 </span>            : 
<span class="lineNum">     270 </span>            : #endif                                  /* } */
<span class="lineNum">     271 </span>            : 
<span class="lineNum">     272 </span>            : 
<span class="lineNum">     273 </span>            : /* arrays larger than 'RANLIMIT' may use randomized pivots */
<span class="lineNum">     274 </span>            : #define RANLIMIT        100u
<span class="lineNum">     275 </span>            : 
<span class="lineNum">     276 </span>            : 
<span class="lineNum">     277 </span><span class="lineCov">      43026 : static void set2 (lua_State *L, IdxT i, IdxT j) {</span>
<span class="lineNum">     278 </span><span class="lineCov">      43026 :   lua_seti(L, 1, i);</span>
<span class="lineNum">     279 </span><span class="lineCov">      43026 :   lua_seti(L, 1, j);</span>
<span class="lineNum">     280 </span><span class="lineCov">      43026 : }</span>
<span class="lineNum">     281 </span>            : 
<span class="lineNum">     282 </span>            : 
<span class="lineNum">     283 </span>            : /*
<span class="lineNum">     284 </span>            : ** Return true iff value at stack index 'a' is less than the value at
<span class="lineNum">     285 </span>            : ** index 'b' (according to the order of the sort).
<span class="lineNum">     286 </span>            : */
<span class="lineNum">     287 </span><span class="lineCov">      91614 : static int sort_comp (lua_State *L, int a, int b) {</span>
<span class="lineNum">     288 </span><span class="lineCov">      91614 :   if (lua_isnil(L, 2))  /* no function? */</span>
<span class="lineNum">     289 </span><span class="lineCov">      91608 :     return lua_compare(L, a, b, LUA_OPLT);  /* a &lt; b */</span>
<span class="lineNum">     290 </span>            :   else {  /* function */
<span class="lineNum">     291 </span>            :     int res;
<span class="lineNum">     292 </span><span class="lineCov">          6 :     lua_pushvalue(L, 2);    /* push function */</span>
<span class="lineNum">     293 </span><span class="lineCov">          6 :     lua_pushvalue(L, a-1);  /* -1 to compensate function */</span>
<span class="lineNum">     294 </span><span class="lineCov">          6 :     lua_pushvalue(L, b-2);  /* -2 to compensate function and 'a' */</span>
<span class="lineNum">     295 </span><span class="lineCov">          6 :     lua_call(L, 2, 1);      /* call function */</span>
<span class="lineNum">     296 </span><span class="lineCov">          6 :     res = lua_toboolean(L, -1);  /* get result */</span>
<span class="lineNum">     297 </span><span class="lineCov">          6 :     lua_pop(L, 1);          /* pop result */</span>
<span class="lineNum">     298 </span><span class="lineCov">          6 :     return res;</span>
<span class="lineNum">     299 </span>            :   }
<span class="lineNum">     300 </span>            : }
<span class="lineNum">     301 </span>            : 
<span class="lineNum">     302 </span>            : 
<span class="lineNum">     303 </span>            : /*
<span class="lineNum">     304 </span>            : ** Does the partition: Pivot P is at the top of the stack.
<span class="lineNum">     305 </span>            : ** precondition: a[lo] &lt;= P == a[up-1] &lt;= a[up],
<span class="lineNum">     306 </span>            : ** so it only needs to do the partition from lo + 1 to up - 2.
<span class="lineNum">     307 </span>            : ** Pos-condition: a[lo .. i - 1] &lt;= a[i] == P &lt;= a[i + 1 .. up]
<span class="lineNum">     308 </span>            : ** returns 'i'.
<span class="lineNum">     309 </span>            : */
<span class="lineNum">     310 </span><span class="lineCov">       9937 : static IdxT partition (lua_State *L, IdxT lo, IdxT up) {</span>
<span class="lineNum">     311 </span><span class="lineCov">       9937 :   IdxT i = lo;  /* will be incremented before first use */</span>
<span class="lineNum">     312 </span><span class="lineCov">       9937 :   IdxT j = up - 1;  /* will be decremented before first use */</span>
<span class="lineNum">     313 </span>            :   /* loop invariant: a[lo .. i] &lt;= P &lt;= a[j .. up] */
<span class="lineNum">     314 </span>            :   for (;;) {
<span class="lineNum">     315 </span>            :     /* next loop: repeat ++i while a[i] &lt; P */
<span class="lineNum">     316 </span><span class="lineCov">      23966 :     while (lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) {</span>
<span class="lineNum">     317 </span><span class="lineCov">      10406 :       if (i == up - 1)  /* a[i] &lt; P  but a[up - 1] == P  ?? */</span>
<span class="lineNum">     318 </span><span class="lineCov">          1 :         luaL_error(L, &quot;invalid order function for sorting&quot;);</span>
<span class="lineNum">     319 </span><span class="lineCov">      10405 :       lua_pop(L, 1);  /* remove a[i] */</span>
<span class="lineNum">     320 </span>            :     }
<span class="lineNum">     321 </span>            :     /* after the loop, a[i] &gt;= P and a[lo .. i - 1] &lt; P */
<span class="lineNum">     322 </span>            :     /* next loop: repeat --j while P &lt; a[j] */
<span class="lineNum">     323 </span><span class="lineCov">      23964 :     while (lua_geti(L, 1, --j), sort_comp(L, -3, -1)) {</span>
<span class="lineNum">     324 </span><span class="lineCov">      10404 :       if (j &lt; i)  /* j &lt; i  but  a[j] &gt; P ?? */</span>
<span class="lineNum">     325 </span><span class="lineNoCov">          0 :         luaL_error(L, &quot;invalid order function for sorting&quot;);</span>
<span class="lineNum">     326 </span><span class="lineCov">      10404 :       lua_pop(L, 1);  /* remove a[j] */</span>
<span class="lineNum">     327 </span>            :     }
<span class="lineNum">     328 </span>            :     /* after the loop, a[j] &lt;= P and a[j + 1 .. up] &gt;= P */
<span class="lineNum">     329 </span><span class="lineCov">      13560 :     if (j &lt; i) {  /* no elements out of place? */</span>
<span class="lineNum">     330 </span>            :       /* a[lo .. i - 1] &lt;= P &lt;= a[j + 1 .. i .. up] */
<span class="lineNum">     331 </span><span class="lineCov">       9936 :       lua_pop(L, 1);  /* pop a[j] */</span>
<span class="lineNum">     332 </span>            :       /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */
<span class="lineNum">     333 </span><span class="lineCov">       9936 :       set2(L, up - 1, i);</span>
<span class="lineNum">     334 </span><span class="lineCov">       9936 :       return i;</span>
<span class="lineNum">     335 </span>            :     }
<span class="lineNum">     336 </span>            :     /* otherwise, swap a[i] - a[j] to restore invariant and repeat */
<span class="lineNum">     337 </span><span class="lineCov">       3624 :     set2(L, i, j);</span>
<span class="lineNum">     338 </span>            :   }
<span class="lineNum">     339 </span>            : }
<span class="lineNum">     340 </span>            : 
<span class="lineNum">     341 </span>            : 
<span class="lineNum">     342 </span>            : /*
<span class="lineNum">     343 </span>            : ** Choose an element in the middle (2nd-3th quarters) of [lo,up]
<span class="lineNum">     344 </span>            : ** &quot;randomized&quot; by 'rnd'
<span class="lineNum">     345 </span>            : */
<span class="lineNum">     346 </span><span class="lineNoCov">          0 : static IdxT choosePivot (IdxT lo, IdxT up, unsigned int rnd) {</span>
<span class="lineNum">     347 </span><span class="lineNoCov">          0 :   IdxT r4 = (up - lo) / 4;  /* range/4 */</span>
<span class="lineNum">     348 </span><span class="lineNoCov">          0 :   IdxT p = rnd % (r4 * 2) + (lo + r4);</span>
<span class="lineNum">     349 </span>            :   lua_assert(lo + r4 &lt;= p &amp;&amp; p &lt;= up - r4);
<span class="lineNum">     350 </span><span class="lineNoCov">          0 :   return p;</span>
<span class="lineNum">     351 </span>            : }
<span class="lineNum">     352 </span>            : 
<span class="lineNum">     353 </span>            : 
<span class="lineNum">     354 </span>            : /*
<span class="lineNum">     355 </span>            : ** QuickSort algorithm (recursive function)
<span class="lineNum">     356 </span>            : */
<span class="lineNum">     357 </span><span class="lineCov">      15853 : static void auxsort (lua_State *L, IdxT lo, IdxT up,</span>
<span class="lineNum">     358 </span>            :                                    unsigned int rnd) {
<span class="lineNum">     359 </span><span class="lineCov">      25789 :   while (lo &lt; up) {  /* loop for tail recursion */</span>
<span class="lineNum">     360 </span>            :     IdxT p;  /* Pivot index */
<span class="lineNum">     361 </span>            :     IdxT n;  /* to be used later */
<span class="lineNum">     362 </span>            :     /* sort elements 'lo', 'p', and 'up' */
<span class="lineNum">     363 </span><span class="lineCov">      20509 :     lua_geti(L, 1, lo);</span>
<span class="lineNum">     364 </span><span class="lineCov">      20509 :     lua_geti(L, 1, up);</span>
<span class="lineNum">     365 </span><span class="lineCov">      20509 :     if (sort_comp(L, -1, -2))  /* a[up] &lt; a[lo]? */</span>
<span class="lineNum">     366 </span><span class="lineCov">      10256 :       set2(L, lo, up);  /* swap a[lo] - a[up] */</span>
<span class="lineNum">     367 </span>            :     else
<span class="lineNum">     368 </span><span class="lineCov">      10253 :       lua_pop(L, 2);  /* remove both values */</span>
<span class="lineNum">     369 </span><span class="lineCov">      20509 :     if (up - lo == 1)  /* only 2 elements? */</span>
<span class="lineNum">     370 </span><span class="lineCov">       6602 :       return;  /* already sorted */</span>
<span class="lineNum">     371 </span><span class="lineCov">      13907 :     if (up - lo &lt; RANLIMIT || rnd == 0)  /* small interval or no randomize? */</span>
<span class="lineNum">     372 </span><span class="lineCov">      13907 :       p = (lo + up)/2;  /* middle element is a good pivot */</span>
<span class="lineNum">     373 </span>            :     else  /* for larger intervals, it is worth a random pivot */
<span class="lineNum">     374 </span><span class="lineNoCov">          0 :       p = choosePivot(lo, up, rnd);</span>
<span class="lineNum">     375 </span><span class="lineCov">      13907 :     lua_geti(L, 1, p);</span>
<span class="lineNum">     376 </span><span class="lineCov">      13907 :     lua_geti(L, 1, lo);</span>
<span class="lineNum">     377 </span><span class="lineCov">      13907 :     if (sort_comp(L, -2, -1))  /* a[p] &lt; a[lo]? */</span>
<span class="lineNum">     378 </span><span class="lineCov">       4639 :       set2(L, p, lo);  /* swap a[p] - a[lo] */</span>
<span class="lineNum">     379 </span>            :     else {
<span class="lineNum">     380 </span><span class="lineCov">       9268 :       lua_pop(L, 1);  /* remove a[lo] */</span>
<span class="lineNum">     381 </span><span class="lineCov">       9268 :       lua_geti(L, 1, up);</span>
<span class="lineNum">     382 </span><span class="lineCov">       9268 :       if (sort_comp(L, -1, -2))  /* a[up] &lt; a[p]? */</span>
<span class="lineNum">     383 </span><span class="lineCov">       4634 :         set2(L, p, up);  /* swap a[up] - a[p] */</span>
<span class="lineNum">     384 </span>            :       else
<span class="lineNum">     385 </span><span class="lineCov">       4634 :         lua_pop(L, 2);</span>
<span class="lineNum">     386 </span>            :     }
<span class="lineNum">     387 </span><span class="lineCov">      13907 :     if (up - lo == 2)  /* only 3 elements? */</span>
<span class="lineNum">     388 </span><span class="lineCov">       3970 :       return;  /* already sorted */</span>
<span class="lineNum">     389 </span><span class="lineCov">       9937 :     lua_geti(L, 1, p);  /* get middle element (Pivot) */</span>
<span class="lineNum">     390 </span><span class="lineCov">       9937 :     lua_pushvalue(L, -1);  /* push Pivot */</span>
<span class="lineNum">     391 </span><span class="lineCov">       9937 :     lua_geti(L, 1, up - 1);  /* push a[up - 1] */</span>
<span class="lineNum">     392 </span><span class="lineCov">       9937 :     set2(L, p, up - 1);  /* swap Pivot (a[p]) with a[up - 1] */</span>
<span class="lineNum">     393 </span><span class="lineCov">       9937 :     p = partition(L, lo, up);</span>
<span class="lineNum">     394 </span>            :     /* a[lo .. p - 1] &lt;= a[p] == P &lt;= a[p + 1 .. up] */
<span class="lineNum">     395 </span><span class="lineCov">       9936 :     if (p - lo &lt; up - p) {  /* lower interval is smaller? */</span>
<span class="lineNum">     396 </span><span class="lineCov">       4008 :       auxsort(L, lo, p - 1, rnd);  /* call recursively for lower interval */</span>
<span class="lineNum">     397 </span><span class="lineCov">       4008 :       n = p - lo;  /* size of smaller interval */</span>
<span class="lineNum">     398 </span><span class="lineCov">       4008 :       lo = p + 1;  /* tail call for [p + 1 .. up] (upper interval) */</span>
<span class="lineNum">     399 </span>            :     }
<span class="lineNum">     400 </span>            :     else {
<span class="lineNum">     401 </span><span class="lineCov">       5928 :       auxsort(L, p + 1, up, rnd);  /* call recursively for upper interval */</span>
<span class="lineNum">     402 </span><span class="lineCov">       5928 :       n = up - p;  /* size of smaller interval */</span>
<span class="lineNum">     403 </span><span class="lineCov">       5928 :       up = p - 1;  /* tail call for [lo .. p - 1]  (lower interval) */</span>
<span class="lineNum">     404 </span>            :     }
<span class="lineNum">     405 </span><span class="lineCov">       9936 :     if ((up - lo) / 128 &gt; n) /* partition too imbalanced? */</span>
<span class="lineNum">     406 </span><span class="lineNoCov">          0 :       rnd = l_randomizePivot();  /* try a new randomization */</span>
<span class="lineNum">     407 </span>            :   }  /* tail call auxsort(L, lo, up, rnd) */
<span class="lineNum">     408 </span>            : }
<span class="lineNum">     409 </span>            : 
<span class="lineNum">     410 </span>            : 
<span class="lineNum">     411 </span><span class="lineCov">       5918 : static int sort (lua_State *L) {</span>
<span class="lineNum">     412 </span><span class="lineCov">       5918 :   lua_Integer n = aux_getn(L, 1, TAB_RW);</span>
<span class="lineNum">     413 </span><span class="lineCov">       5918 :   if (n &gt; 1) {  /* non-trivial interval? */</span>
<span class="lineNum">     414 </span><span class="lineCov">       5917 :     luaL_argcheck(L, n &lt; INT_MAX, 1, &quot;array too big&quot;);</span>
<span class="lineNum">     415 </span><span class="lineCov">       5917 :     if (!lua_isnoneornil(L, 2))  /* is there a 2nd argument? */</span>
<span class="lineNum">     416 </span><span class="lineCov">          2 :       luaL_checktype(L, 2, LUA_TFUNCTION);  /* must be a function */</span>
<span class="lineNum">     417 </span><span class="lineCov">       5917 :     lua_settop(L, 2);  /* make sure there are two arguments */</span>
<span class="lineNum">     418 </span><span class="lineCov">       5917 :     auxsort(L, 1, (IdxT)n, 0);</span>
<span class="lineNum">     419 </span>            :   }
<span class="lineNum">     420 </span><span class="lineCov">       5917 :   return 0;</span>
<span class="lineNum">     421 </span>            : }
<span class="lineNum">     422 </span>            : 
<span class="lineNum">     423 </span>            : /* }====================================================== */
<span class="lineNum">     424 </span>            : 
<span class="lineNum">     425 </span>            : 
<span class="lineNum">     426 </span>            : static const luaL_Reg tab_funcs[] = {
<span class="lineNum">     427 </span>            :   {&quot;concat&quot;, tconcat},
<span class="lineNum">     428 </span>            : #if defined(LUA_COMPAT_MAXN)
<span class="lineNum">     429 </span>            :   {&quot;maxn&quot;, maxn},
<span class="lineNum">     430 </span>            : #endif
<span class="lineNum">     431 </span>            :   {&quot;insert&quot;, tinsert},
<span class="lineNum">     432 </span>            :   {&quot;pack&quot;, pack},
<span class="lineNum">     433 </span>            :   {&quot;unpack&quot;, unpack},
<span class="lineNum">     434 </span>            :   {&quot;remove&quot;, tremove},
<span class="lineNum">     435 </span>            :   {&quot;move&quot;, tmove},
<span class="lineNum">     436 </span>            :   {&quot;sort&quot;, sort},
<span class="lineNum">     437 </span>            :   {NULL, NULL}
<span class="lineNum">     438 </span>            : };
<span class="lineNum">     439 </span>            : 
<span class="lineNum">     440 </span>            : 
<span class="lineNum">     441 </span><span class="lineCov">         87 : LUAMOD_API int luaopen_table (lua_State *L) {</span>
<span class="lineNum">     442 </span><span class="lineCov">         87 :   luaL_newlib(L, tab_funcs);</span>
<span class="lineNum">     443 </span>            : #if defined(LUA_COMPAT_UNPACK)
<span class="lineNum">     444 </span>            :   /* _G.unpack = table.unpack */
<span class="lineNum">     445 </span>            :   lua_getfield(L, -1, &quot;unpack&quot;);
<span class="lineNum">     446 </span>            :   lua_setglobal(L, &quot;unpack&quot;);
<span class="lineNum">     447 </span>            : #endif
<span class="lineNum">     448 </span><span class="lineCov">         87 :   return 1;</span>
<span class="lineNum">     449 </span>            : }
<span class="lineNum">     450 </span>            : 
</pre>
      </td>
    </tr>
  </table>
  <br>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
    <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LCOV version 1.13</a></td></tr>
  </table>
  <br>

</body>
</html>
